package com.test.comlection;

import org.w3c.dom.Node;

public class LinkedList<E> {

    //链表的头节点，用于连接之后的所有节点
    private final Node<E> head =new Node<E>(null);
    private int size=0;   //当前的元素存一下，方便后面的操作

    //添加操作
    public void add(E element,int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("插入的位置不合法，合法的插入位置为:0 ~"+size);
        Node<E> prev =head;//先找到对应的位置的前驱节点
        for (int i=0;i<index;i++){
            prev = prev.next;
        }//从头部节点开始找，找到想要插入位置，设此为BC之间，则这里指向的节点为B节点
        Node<E> node =new Node<>(element);//创建新的节点
        node.next=prev.next;//先让新的节点指向B原本指向的节点，也就是C点
        prev.next=node;//然后让B点指向新的节点
        size++;//更新size

    }

    //删除操作
    public E remove(int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("删除位置不合法，合法位置为0~"+(size-1));
        Node<E> prev =head;
        for (int i=0;i<index;i++)
            prev = prev.next;

        E e =prev.next.element;
        prev.next=prev.next.next;
        size--;
        return e;

    }

    //获取对应位置上的元素
    public E get(int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("非法位置，合法位置为0~"+(size-1));
        Node<E> node =head;
        while(index-->=0){
            node = node.next;
        }
        return node.element;
    }
    //获取链表容量
    public int getSize(){
        return size;
    }

    @Override
    public String toString(){
        StringBuilder builder=new StringBuilder();
        Node<E> node=head.next; //从第一个节点开始，一个一个遍历，遍历一个就拼接到字符串上去
        while (node!=null){
            builder.append(node.element).append("  ");
            node=node.next;
        }
        return builder.toString();
    }

    private static class Node<E> {  //节点类，内部使用

        private  E element;//每个节点都存放元素
        private Node<E> next;//以及指向下一个结点的引用

        public Node(E e){
            this.element = e;
        }
    }
}
